package cn.com.mdx.collection.queue;

import java.util.Iterator;

/*
 * @author huangyuan
 * @description 队列 - 可变数组实现
 */
@SuppressWarnings("unchecked")
public class ResizingArrayQueue<Item> implements Iterable<Item> {

    /**
     * 初始化数组默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 队列容量
     */
    private int size;
    /**
     * 队列对象数组
     */
    private Item[] items;
    /**
     * 队列头部指针，用于取队列中的数据
     */
    private int first;

    private int last;

    public ResizingArrayQueue() {
        size = 0;
        first = 0;
        last = 0;
        items = (Item[]) new Object[DEFAULT_CAPACITY];
    }

    /**
     * @param item 入队列数据
     * @return void
     * @Author huangy
     * @description //TODO 入队列
     * @date 5:16 下午 2020/8/12
     **/
    public void enqueue(Item item) {
        //队列容量等于数组容量，将数组容量扩大到原来的2倍
        if(size + 1 == items.length) resize(items.length * 2);
        items[last++] = item;
        if(last == items.length) last = 0;//环绕利用数组
        size++;
    }

    /**
     * @return Item 返回的数据
     * @Author huangy
     * @description //TODO 出队列
     * @date 5:17 下午 2020/8/12
     **/
    public Item dequeue() {
        if (isEmpty()) throw new UnsupportedOperationException("队列为空");
        //队列容量如果为数组容量额1/4，将数组容量缩小为原来的1/2 不缩小为原来的两倍，是防止在临界值频繁的增删操作引起数组长度的震荡
        if(size - 1 <= items.length / 4) resize(items.length / 2);
        Item item = items[first];
        items[first++] = null;
        size--;//数组容量减1
        if(first == items.length) first = 0; //环绕利用数组
        return item;
    }

    /**
     * @return int 队列容量
     * @Author huangy
     * @description //TODO 队列容量
     * @date 5:18 下午 2020/8/12
     **/
    public int size() {
        return size;
    }

    /**
     * @return boolean true 表示空 false 表示不为空
     * @Author huangy
     * @description //TODO 查看队列是否为空
     * @date 5:18 下午 2020/8/12
     **/
    public boolean isEmpty() {
        return size == 0;
    }

    private class ResizingArrayQueueIterator implements Iterator<Item> {
        int index = first;
        @Override
        public boolean hasNext() {
            return index < last;
        }

        @Override
        public Item next() {
            return items[index++];
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new ResizingArrayQueueIterator();
    }

    /**
     * @param arrayLength 要重置的长度
     * @return void
     * @Author huangy
     * @description //TODO 重置数组长度
     * @date 8:55 下午 2020/8/12
     **/
    private void resize(int arrayLength) {
        assert size  > items.length;
        Item[] newArray = (Item[]) new Object[arrayLength];
        for (int i = 0; i < size; i++) {
            newArray[i] = items[first++];
        }
        first = 0;
        last = size;
        items = newArray;
    }

    public static void main(String[] args) {
        ResizingArrayQueue<Integer> resizingArrayQueue = new ResizingArrayQueue<>();
        for (int i = 0; i < 100; i++) {
            resizingArrayQueue.enqueue(i);
        }
        System.out.println("---------------------------");
        for(int num: resizingArrayQueue){
            System.out.println(num);
        }
        System.out.println("---------------------------");
        for (int i = 0; i < 50; i++) {
            System.out.println(resizingArrayQueue.dequeue());
        }
        System.out.println("---------------------------");
        for (Integer num: resizingArrayQueue) {
            System.out.println(num);
        }
    }
}
